package com.leetcode.根据算法进行分类.动态规划算法相关;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author: xiaomi
 * @date: 2021/3/27
 * @description: 01背包问题
 * https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/oexm1h/
 * 笔试模式，使用 Scan 的方式
 */
public class X_01背包问题 {

    //param 1
    static int weightSum = 0;
    //param 2
    static int[] weights = new int[0];
    //param 3
    static int[] values = new int[0];
    static int len = 0;
    static int endIndex = 0;
    static int res = 0;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String nextLine = scanner.nextLine();
        int sum = 0;

        while (sum < 3 || (nextLine != null && !nextLine.equals(""))) {
            //sum += Integer.parseInt(nextLine);
            sum++;
            switch (sum) {
                case 1:
                    weightSum = Integer.parseInt(nextLine);
                    break;
                case 2:
                    String[] splits = nextLine.split("\\s");
                    weights = new int[splits.length];
                    int index = 0;
                    for (String item :
                            splits) {
                        weights[index++] = Integer.parseInt(item);
                    }
                    break;
                case 3:
                    String[] vs = nextLine.split("\\s");
                    values = new int[vs.length];
                    int i = 0;
                    for (String item :
                            vs) {
                        values[i++] = Integer.parseInt(item);
                    }
                    break;
                default:
                    break;
            }
            //System.out.println(sum);
            nextLine = scanner.nextLine();
        }
        //
//        System.out.println("开始计算");
//        System.out.println("weightSum = " + weightSum);
//        System.out.println("weights = " + Arrays.toString(weights));
//        System.out.println("values = " + Arrays.toString(values));
        len = weights.length;
        endIndex = len - 1;

        putBagsByBackTrack();
        System.out.println(res);
    }

    /**
     *
     */
    private static void putBagsByBackTrack() {
        LinkedList<Integer> indexList = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            if (weights[i] <= weightSum) {
                indexList.add(i);
                putBagsByBackTrack(weightSum - weights[i], i + 1, indexList);
                //back
                indexList.removeLast();
            }
        }

    }

    private static void putBagsByBackTrack(int left, int beginIndex, LinkedList<Integer> indexList) {
        if (beginIndex == len || left < weights[endIndex]) {
            //如果已经到达结束
            int temp = 0;
            for (Integer item :
                    indexList) {
                temp += values[item];
            }
            res = Math.max(temp, res);
            return;
        }
        for (int i = beginIndex; i < len; i++) {
            if (weights[i] <= left) {
                indexList.add(i);
                putBagsByBackTrack(left - weights[i], i + 1, indexList);

                //back
                indexList.removeLast();

            } else {
                continue;
            }
        }

    }


}
